import java.util.*;

public class Test {
}
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        Map<Integer,ListNode> map = new HashMap<>();
        ListNode dim = new ListNode(0);
        dim.next = head;
        int prevSum = 0;
        for(ListNode node=dim; node != null; node = node.next){
            prevSum += node.val;
            map.put(prevSum,node);
        }
        prevSum = 0;
        for(ListNode node=dim; node != null; node = node.next){
            prevSum += node.val;
            node.next = map.get(prevSum).next;
        }
        return dim.next;
    }
}
class Solution3 {
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        ListNode prev = new ListNode();
        while(cur != null){
            if(set.contains(cur.val)){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                set.add(cur.val);
                prev.next = cur;
                prev = prev.next;
                cur = cur.next;
            }
        }
        return head;
    }
}
class ListNode {
   int val;
     ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

